package com.leetcode.LeetCode精选TOP面试题;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @author 覃国强
 * @date 2022-06-29 17:39
 */
public class 题库_0140_单词拆分II {

  static
  class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
      List<String> answer = new ArrayList<>();
      if (s == null || s.length() == 0 || wordDict == null || wordDict.isEmpty()) {
        return answer;
      }
      backtrack(s, 0, new ArrayDeque<>(), wordDict, answer);
      return answer;
    }

    private void backtrack(String s, int toffset, Deque<String> sentence, List<String> wordDict, List<String> answer) {
      if (toffset == s.length()) {
        StringBuilder sb = new StringBuilder();
        for (String word : sentence) {
          if (sb.length() != 0) {
            sb.append(" ");
          }
          sb.append(word);
        }
        answer.add(sb.toString());
        return;
      }

      for (String prefix : wordDict) {
        if (s.startsWith(prefix, toffset)) {
          sentence.addLast(prefix);
          backtrack(s, toffset + prefix.length(), sentence, wordDict, answer);
          sentence.removeLast();
        }
      }
    }
  }

}
